package two.chapter_2.c2_1;

public class Ex2_1_2 {

    /**
     * 在选择排序中，一个元素最多可能被交换多少次？平均可能会被交换多少次？
     * @param args
     */
    public static void main(String [] args){

    }

    private class Selection<Item extends Comparable<Item>> extends Sortable<Item>{
        /**
         * 最坏的情况 比较次数  N-1+N-2+...+1=N(N-1)/2
         *           交换次数 N
         * 最好的情况 比较次数  N-1+N-2+...+1=N(N-1)/2
         *           交换次数 N
         *
         * 所以平均情况  比较次数为N(N-1)/2
         *             交换次数为N
         * @param items
         */
        @Override
        public void sort(Item[] items) {
            for (int i=0;i<items.length;i++){
                int minIndex=i;
                for (int j=i+1;j<items.length;j++){
                    if (less(items[j],items[minIndex])){
                        //exch(j,minIndex,items);
                        minIndex=j;
                    }
                }
                exch(i,minIndex,items);
            }
        }
    }
}
